package com.goodwill.androidtest.tree_test;

import com.goodwill.androidtest.tree_test.printer.BinaryTreeInfo;

import java.util.Comparator;

/**
 * @author guoxiaojun
 * @date 2022/1/7 15:33
 * @desc 自定义二叉树
 */
public class BinarySearchTree<E> implements BinaryTreeInfo {

    private int size;
    private Node<E> rootNode;
    private Comparator comparator;

    public BinarySearchTree() {
    }

    public BinarySearchTree(Comparator comparator) {
        this.comparator = comparator;
    }

    public int size() {
        return size;
    }

    public void push(E e) {
        //root node
        if (rootNode == null) {
            rootNode = new Node<>(e, null);
            return;
        }

        Node<E> parent = rootNode;
        Node<E> node = rootNode;

        int compare = 0;
        while (node != null) {
            parent = node;
            compare = compare(e, node.element);
            if (compare < 1) {
                node = node.left;
            } else if (compare > 1) {
                node = node.right;
            } else {
                node.element = e;
                return;
            }
        }

        Node<E> newNode = new Node<>(e, parent);
        if (compare < 1) {
            parent.left = newNode;
        } else if (compare > 1) {
            parent.right = newNode;
        }

        size++;
    }

    @Override
    public Object root() {
        return rootNode;
    }

    @Override
    public Object left(Object node) {
        return node == null? null: ((Node)node).left;
    }

    @Override
    public Object right(Object node) {
        return node == null? null: ((Node)node).right;
    }

    @Override
    public Object string(Object node) {
        return node == null? null: ((Node)node).element;
    }

    class Node<E> {
        private E element;
        private Node<E> left;
        private Node<E> right;
        private Node<E> parent;

        public Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }
    }

    int compare(E e1, E e2) {
        if (comparator != null) {
            return comparator.compare(e1, e2);
        }

        return ((Comparable) e1).compareTo(e2);
    }
}
